package 动态规划.可dp可二分;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/5 19:28
 */
public class leetcode1478安排邮筒 {
    /*
        这道题感觉 和 ，数组分成k 组求最大值，有点类似，但又不一样！
        非常的相似
        *****
        这个题 真的 很牛逼！
        这个题 必须 之际记在心里面去
     */

    public int solution(int nums[],int k){
        // 需要 对数组 进行一个 排序!
        Arrays.sort(nums);

        int len = nums.length;
        /*
         *L。。。。R minDistance[l][r] 表示的是 在 l----r 之间 只有 一个 邮筒安排的 时候
         * 的最小 距离和
         */
        int minDistance [][] = new int [len + 1][len + 1];
        for(int L = 0;L < len;L++ ){
            // 因 为 R >= L (这是 距离) 因为 只有一个  坐标 那么 最小距离  就是 0
            for(int R = L + 1;R < len;R++){
                // 这段代码 非常的巧妙的 , 这个 思想就非常的巧妙 !
                minDistance[L][R] = minDistance[L][R - 1] + nums[R] - nums[L + R >> 1];
            }
        }


        return recursion(0,k,minDistance,len);
    }
    /*
        理解了怎么回事的话, 那这个题就是 跟  数组 分成 k 组的 题, 相似了
     */
    public int recursion(int index,int k,int dis[][] ,int len){
        // 一定要 把 k 给用完 ,只有 把 k 用完,得到的 距离才是最小距离
        if(index == len)
            return k == 0 ? 0 : Integer.MAX_VALUE;
        /*
          这里是 非常核心的一点,
          对于暴力递归来说,
          下面这个basecase 设置不设置都可以, 因为  不写下面这个basecase 的时候 当 k == 0 时,会 继续递归,这个时候 k 可能就 是 负值
          但是 最终 还是会 到达 inddx == len 被 第一个 basecase 给 拦截 ,然后 返回Integer.MAX_VALUE
          所以 加上这个递归, 就是 为了 提前 返回 ,别整那么多层 递归了
          但是 在 dp 中 不写 这个 basecase 可就是 有问题了, 因为 k 的索引 不能 为 负 值
         */
        if(k == 0)
            return Integer.MAX_VALUE;
        int ans = Integer.MAX_VALUE;
        for(int scale = 1;index + scale <= len;scale ++){
            int temp = recursion(index + scale,k - 1 ,dis,len);
            // 这里 和前缀和的处理 就很不一样了!
            ans = Math.min(ans,temp == Integer.MAX_VALUE ? temp : temp + dis[index][index + scale - 1]);
        }
        return ans;
    }

    public int dp(int nums[],int k){
        // 需要 对数组 进行一个 排序!
        Arrays.sort(nums);
        int len = nums.length;
        /*
         *L。。。。R minDistance[l][r] 表示的是 在 l----r 之间 只有 一个 邮筒安排的 时候
         * 的最小 距离和
         */
        int minDistance [][] = new int [len + 1][len + 1];
        for(int L = 0;L < len;L++ ){
            // 因 为 R >= L (这是 距离) 因为 只有一个  坐标 那么 最小距离  就是 0
            for(int R = L + 1;R < len;R++){
                // 这段代码 非常的巧妙的 , 这个 思想就非常的巧妙 !
                minDistance[L][R] = minDistance[L][R - 1] + nums[R] - nums[L + R >> 1];
            }
        }
        // dp 表
        int dp [][] = new int [len + 1][len + 1];
        for(int i = 0;i <= k;i++){
            dp[len][i] = Integer.MAX_VALUE;
        }
        for(int i = 0;i <= len;i++ ){
            dp[i][0] = Integer.MAX_VALUE;
        }
        dp[len][0] = 0;
        for(int index = len - 1;index >= 0;index -- ){
            //   len  - index 是 房子的数量, x 是邮局的个数 如果 x >= len - index 不用算 最小距离就是 0 ,这里做了一个小小的优化
            // 但是这个优化 ,其实 影响 的效率不大好像, 从结果上来看
            for(int x = 1; x <= Math.min(len - index,k);x++){
                int ans = Integer.MAX_VALUE;
                /*
                为啥  需要 一个 三目 表达式的判断呢
                还是这里的 取值 有关系
                我是把  取不到 最优 解的 地方直接设置为 Integer的最大值,以便判断
                但是 设置这个值的问题在于,就会溢出, 因为会涉及到 MAX + 另外一个值,直接 就爆 int 了
                导致结果错误!
                其实 可以设置成 MAX/2  代码可能会更优雅一些
                 */
                for(int scale = 1;index + scale <= len;scale ++){
                    ans = Math.min(ans,dp[index + scale][x - 1] == Integer.MAX_VALUE ? dp[index + scale][x - 1] : dp[index + scale][x - 1] + minDistance[index][index + scale - 1]);
                }
                dp[index][x] = ans;
            }
        }
        return dp[0][k];
    }

}
